package offer;

@FunctionalInterface
public interface MaximumDifference {
    /**
     * Given a 0-indexed integer array nums of size n, find the maximum difference between nums[i] and nums[j] (i.e., nums[j] - nums[i]), such that 0 <= i < j < n and nums[i] < nums[j].
     *
     * Return the maximum difference. If no such i and j exists, return -1.
     *
     * @param nums      array
     * @return          the maximum difference or -1
     */
    int maximumDifference(int[] nums);
}

class MaximumDifferenceTest {

    static final int[] TEST_01 = new int[]{7,1,5,4};
    static final int[] TEST_02 = new int[]{1,5,2,10};
    public static void main(String[] args) {
       int a =  new MaximumDifferenceImpl1().maximumDifference(TEST_02);
        System.out.println(a);
    }
}

class MaximumDifferenceImpl1 implements MaximumDifference{

    /**
     * 时间复杂度o(nlogn),空间复杂度o(nlogn)用了递归
     * 特殊情况，数组为递减序列，返回-1，否则一定有一个大于0的合法答案
     * 给定一个区间中点 mid ， i ， j 的分布可能为
     * i <= mid , j > mid        此情况需要寻找左侧区间的最小值，mid右侧区间的最大值
     * i < j < mid               此情况
     * mid < i < j
     * @param nums      array
     * @return          the maximum difference or -1
     */
    @Override
    public int maximumDifference(int[] nums) {
        return maximumDifferenceHelper(nums, 0, nums.length - 1);
    }
    private int maximumDifferenceHelper(int[] nums, int lower, int upper){
        if(lower >= upper){
            return -1;
        }else if(lower == upper - 1){
            if(nums[lower] < nums[upper]){
                return nums[upper] - nums[lower];
            }else{
                return -1;
            }
        }
        int mid = lower + (upper - lower) / 2;
        int leftMin = Integer.MAX_VALUE;
        for(int i = lower; i <= mid; i++){
            if(nums[i] < leftMin){
                leftMin = nums[i];
            }
        }
        int rightMax = Integer.MIN_VALUE;
        for(int i = mid + 1; i <= upper; i++){
            if(nums[i] > rightMax){
                rightMax = nums[i];
            }
        }
        int midCandidate = rightMax - leftMin > 0 ? rightMax - leftMin : -1;
        int leftCandidate = maximumDifferenceHelper(nums, lower, mid);
        int rightCandidate = maximumDifferenceHelper(nums, mid + 1, upper);
        return Math.max(Math.max(midCandidate, rightCandidate), leftCandidate);
    }
}

class MaximumDifferenceImpl2 implements MaximumDifference{
    /**
     * 时间o(n),空间o(1)
     * 抄一遍题解
     * 如果nums[i],nums[j]是一组可行解，则不存在下标k，k < j && k != i使得nums[k] < nums[i]
     * 否则nums[k],nums[j]构成的解比nums[i],nums[j]构成的大，与假设矛盾
     * @param nums      array
     * @return          the maximum difference or -1
     */
    @Override
    public int maximumDifference(int[] nums) {
        int n = nums.length;
        int ans = -1, premin = nums[0];
        for(int i = 1; i < n; i++){
            if(nums[i] > premin){
                ans = Math.max(ans, nums[i] - premin);
            }else {
                premin = nums[i];
            }
        }
        return ans;
    }
}